    Problema 1: De ziua lui M.S. (Catalin Francu)

De ziua lui, M.S. a primit  de la parinti un minunat tort de forma cubica.
Totusi, desi M.S. se uita cu mult jind la tortul cel siropos, parintii nu
vor sa-l lase sa manance pana nu le easpunde la o intrebare. Stiind volumul
deliciosului tort, M.S. trebuie sa afle latura acestuia. Se stie ca tortul
imbietor are latura numar natural. Numele fisierului de intrare se va citi
de la tastatura. Acesta nu va contine decat volumul apetisantului tort,
respectiv un numar intreg care nu depaseste 1000 cifre. datele de intrare
sunt corecte. Numele fisierului de iesire se citeste de asemenea de la
tastatura. In el se va scrie un singur numar, adica latura calculata a
tortului cel gustos. Exemple: Pentru fisierul de intrare 2097152 fisierul de
iesire va contine 128 Pentru fisierul de intrare 10000000000000000000000000000
fisierul de iesire va contine 100000000 Timp limita pentru un test: 10
secunde. ============================================

    Problema 2: Cioplirea numerelor (Marius Popescu)

Se da un numar de N cifre (o secventa de N cifre zecimale, in care prima
nu trebuie sa fie neaparat diferita de zero) cu N < 1000.
a) Sa se elimine K subsecvente disjuncte de cate L cifre consecutive
astfel incat secventa ramasa sa reprezinte numarul cel mai mare care
se poate forma in acest mod (K >= 0, L >= 0, K * L < N). Numarul poate
sa inceapa cu cifra zero.
b) Aceeasi problema, inlocuind "cel mai mare" cu "cel mai mic".

Intrare:
Fisierul de intrare contine zero sau mai multe seturi de date. Fiecare
set de date este format din doua linii. Prima linie contine numerele
N, K si L, in aceasta ordine, separate prin spatii; a doua linie contine
cele N cifre ale numarului, fara spatii.

Iesire:
Pentru fiecare set de date fisierul de iesire trebuie sa contina patru
linii. Prima linie trebuie sa contina pozitiile cifrelor din numarul dat
cu care incep subsecventele care trebuie sterse, in ordine crescatoare,
doua pozitii consecutive fiind separate de exact un spatiu. Pozitiile
cifrelor din numar sunt numerotate de la stanga la dreapta, in ordine
crescatoare, din unu in unu, incepand cu 1. A doua linie va contine
numarul obtinut prin eliminarea subsecventelor descrise pe prima linie
si care trebuie sa fie cel mai mare astfel de numar. Analog, liniile
trei si patru contin raspunsul la punctul (b).
Exemplu:
Intrare:
-------------------------------------------------------
20 2 3
12122212212212121222
10 3 3
0739276145
-------------------------------------------------------
Iesire:
-------------------------------------------------------
1 13
22212212221222
4 8
12112212121222
1 5 8
9
2 5 8
0
-------------------------------------------------------
Timp de executie: 5 secunde pentru un test.
========================================

    Problema 3 (Autostrazi si orase) - Vlad Marius

Intr-o tara exista N orase (N<=100) si M aurostrazi (M<=100). Fiecare
autostrada face legatura intre doua orase. Fiecare autostrada are o taxa
pentru fiecare ora de mers. Aceasta taxa este variabila in timp. La intrarea
cu autoturismul pe o autostrada se plateste taxa pentru toate orele parcurse
pana la iesirea de pe autostrada la valoarea timpului de intrare pe
autostrada. Intr-un oras de pe traseu se poate parca (optional)
autoturismul, dupa care se pleaca pe o autostrada care face legatura cu alt
oras. Fiecare oras are o taxa fixa pentru fiecare ora de parcare in orasul
respectiv. In orasul initial A si orasul final B parcarea este gratuita.
Avand la dispozitie un autoturism personal, trebuie sa ajungeti dintr-un
oras A intr-un oras B astfel incat costul total platit sa fie minim.
Initial, la momentul T=0 va aflati in orasul A iar la momentul TF (TF<=100)
trebuie sa va aflati in orasul B. Fisier de intrare: INPUT.3 N M         -
numarul de orase si numarul de strazi A B TF          - orasul de plecare,
de sosire si timpul alocat deplasarii P1 P1 .. PN     - costul parcarii pe
ora in orasul 1,2,..,N O1 O2 L         - prima autostrada, intre O1 si O2;
distanta dintre ele se parcurge in L ore C(0) C(1).. C(TF-1) - costul pentru
o ora de mers pe prima autostrada daca se intra la momentele 0,1,..,TF-1
.......... O1 O2 L         - a M-a autostrada, intre O1 si O2; distanta
dintre ele se parcurge in L ore C(0) C(1).. C(TF-1) - costul pentru o ora de
mers pe autostrada M daca se intra la momentele 0,1,..,TF-1

Fisier de iesire: OUTPUT.3
C       - costul minim gasit
O       - numarul de orase prin care se trece (inclusiv A si B);
T(1) N(1)   - timp de parcare in orasul A, autostrada care iese din A;
........
T(O-1) N(O-1)   - timp de parcare in orasul O, autostrada care iese din O;
T(O)        - timp de stationare in orasul B;
 Incazul in care nu exista solutie, se va scrie in fisier:
0
0
Exemplu:
Pentru fisierul INPUT.3:
3 2
1 3 5
0 1 0
1 2 2
2 5 5 5 5
2 3 2
5 5 5 1 5
un rezultat corect poate fi:
7
3
0 1
1 2
0

Timp de executie: 10 secunde/test
===================================

    Problema 4 (Distribuitoare)  - Iuliu Vasilescu

Un distribuitor de bile este un aparat cu o intrare si doua iesiri (una
stanga si una dreapta) care functioneaza astfel: pe intrare primeste un sir
de bile pe care le distribuie alternativ prin cele doua iesiri. Deci, prima
bila iese prin stanga, a doua prin dreapta, a treia prin stanga... Sa
consideram acum un arbore format din astfel de distribuitoare. Intr-un
astfel  de arbore bilele se introduc prin varful arborelui si trec succesiv
prin distribuitoare in functie de starea fiecarui distribuitor, pana ajung
la o iesire care nu este conectata la nici un distribuitor; spunem ca atunci
au parasit arborele. Daca iesirea pe care au parasit arborele era iesirea
din stanga a unui distribuitor, atunci se spune ca au parasit arborele prin
stanga; analog pentru celalalt caz. Vom considera in continuare un aparat
format dintr-un astfel de arbore si sub el o tavita cu N bile, numerotate de
la 1 la N, asezate initial in ordine crescatoare de la stanga la dreapta.
Cum functioneaza un astfel de aparat ? La fiecare pas toate bilele sunt
luate din tavita si introduse in arbore, in ordinea in care erau in tavita,
de la stanga la dreapta. Fiecare bila care va parasi arborele prin stanga se
va aseza in tavita in stanga bilelor deja existente in tavita in momentul
caderii ei, si analog, fiecare bila care va p[arasi arborele prin partea
dreapta se va aseza in dreapta bilelor. O bila este introdusa in arbore doar
dupa ce predecesoarea sa a ajuns deja in tavita. Dupa un astfel de pas din
nou toate bilele se vor afla in tavita, dar in alta ordine. Pentru o
configuratie data, sa se calculeze numarul minim  de pasi dupa care bilele
ajung in tavita in ordinea initiala. Observatie: dupa fiecare pas
distribuitoarele sunt "resetate" astfel incat prima bila pe care o vor primi
din pasul urmator o vor arunca prin stanga. Intrare: fisierul INPUT.4 are
urmatoarea structura: n m     - n = numarul de bile, m = numarul de
distribuitoare (1<=n,m<=1000) Ai Bi Ci    - pe fiecare astfel de linie (pana
la sfarsitul fisierului) se ........      gasesc 3 numere cu semnificatia ca
Bi se afla conectat la iesirea stanga a lui Ai, iar Ci la iesirea dreapta a
lui Ai. Daca Ci sau Bi sunt 0, inseamna ca la iesirea corepunzatoare nu se
afla conectata alta intrare. In varf se afla totdeauna distribuitorul 1.
Iesire: fisierul OUTPUT.4 va contine o singura linie, cu numarul de pasi.
Exemplu: INPUT.4 4 4 1 2 3 3 4 0 OUTPUT.4 2

Timp de executie: 5 secunde per test.


--
Adrian Atanasiu             Phone/Fax (home): (0401)638.86.92
                    E-mail: adrian@matem.buc.soros.ro
